public class Test19_1 {
    public static boolean match(String input,String pattern){
        if (input == null || pattern == null) {
            return false;
        }

        return matchCore(input, 0, pattern, 0);
    }
    public static boolean matchCore(String string,int i, String pattern,int p){
        if ( i >= string.length() && p >= pattern.length()) return true;

        if (i != string.length() && p >= pattern.length()) return false;

        //p的下一位置的字符为*
        if (p + 1 < pattern.length() && pattern.charAt(p + 1) == '*') {
            // 匹配串已经结束
            if (i >= string.length()) return matchCore(string,i,pattern,p+2);
            else {
                //匹配串没有结束
                if (pattern.charAt(p) == string.charAt(i) || pattern.charAt(p) == '.') {
                    // 匹配串向后移动一个位置，模式串向后移动两个位置,把p看作出现一次
                    return matchCore(string,i+1,pattern,p+2) ||
                            //匹配串向后移动一个位置，模式串不移动，把p看作多次出现
                            matchCore(string,i+1,pattern,p) ||
                            //匹配串不移动，模式串向后移动两个位置 ，把p看做一次都不出现
                            matchCore(string,i,pattern,p+2);
                }else
                    //如果当前字符和匹配的字符不想等，那么匹配向后移位2个，继续匹配
                    return matchCore(string, i, pattern, p+2);
            }
        }
        // 匹配串已经结束，模式串还没有结束，前面判断了模式串没有结束
        if (i >= string.length()) {
            return false;
        }else {
            //匹配串还未结束，如果当前位置的字符和匹配字符相等，则后一继续匹配
            if (string.charAt(i) == pattern.charAt(p) || pattern.charAt(p) == '.')
                return matchCore(string, i+1, pattern, p+1);
        }
        return false;
    }

    public static void main(String[] args) {
//        System.out.println(match("", "") + "[" + true + "]");
//        System.out.println(match("", ".*") + "[" + false + "]");
//        System.out.println(match("", ".") + "[" + false + "]");
//        System.out.println(match("", "c*") + "[" + true + "]");
//        System.out.println();

//        System.out.println(match("a", ".*") + "[" + true + "]");
//        System.out.println(match("a", "a.") + "[" + false + "]");
//        System.out.println(match("a", "") + "[" + false + "]");
//        System.out.println(match("a", ".") + "[" + true + "]");
//        System.out.println(match("a", "ab*") + "[" + true + "]");
//        System.out.println(match("a", "ab*a") + "[" + false + "]");
//        System.out.println();
        System.out.println(match("aaa", "aab*a"));
//        System.out.println(match("aa", "aa") + "[" + true + "]");
//        System.out.println(match("aa", "a*") + "[" + true + "]");
//        System.out.println(match("aa", ".*") + "[" + true + "]");
//        System.out.println(match("aa", ".") + "[" + false + "]");
//        System.out.println();
//
//        System.out.println(match("ab", ".*") + "[" + true + "]");
//        System.out.println(match("ab", ".*") + "[" + true + "]");

    }
}
